/*
 * @lc app=leetcode.cn id=85 lang=cpp
 *
 * [85] 最大矩形
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        // see each row as columns ~ and use 84.*.cpp
        
        int rowNum = matrix.size();
        int colNum = matrix[0].size();

        vector<vector<int>> height(rowNum, vector<int>(colNum));
        for (int i=0;i<colNum;++i){
            height[0][i] = matrix[0][i] - '0';
        }
        for (int i=1;i<rowNum;++i){
            for (int j=0;j<colNum;++j){
                if (matrix[i][j] == '0'){
                    height[i][j] = 0;
                }else{
                    height[i][j] = 1 + height[i-1][j];
                }
            }
        }

        // // plot
        // for (int i=0;i<rowNum;++i){
        //     for (int j=0;j<colNum;++j){
        //         printf("%d ", height[i][j]);
        //     }
        //     printf("\n");
        // }

        int max = 0, current = 0;

        for (int row=0;row<rowNum;++row){
            current = largestRectangleArea(height[row]);
            // printf("%d %d\n", row, current);
            if (current>max){max = current;}
        }

        return max;
    }
private:
    int largestRectangleArea(vector<int>& heights) {
        std::stack<int> mono;
        int n = heights.size();

        std::vector<int> left(n);
        std::vector<int> right(n);

        // left -> right
        for (int i=0;i<n;++i){
            while (!mono.empty() && 
                    heights[mono.top()] >= heights[i]) {
                mono.pop();
            }
            left[i] = (mono.empty() ? -1 : mono.top());
            mono.push(i);
        }

        mono = std::stack<int>();

        // right -> left
        for (int i=n-1;i>=0;--i){
            while (!mono.empty() && 
                    heights[mono.top()] >= heights[i]) {
                mono.pop();
            }
            right[i] = (mono.empty() ? n : mono.top());
            mono.push(i);
        }

        int max = 0;
        for (int i=0;i<n;++i){
            int current = (right[i] - left[i] - 1)*heights[i];
            if (current>max){max=current;}
        }
        return max;
    }
};
// @lc code=end

